#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int getSeq(int num[], int size)
{
    vector<int> a(num, num+size);
    vector<int> len1(size, 1);
    vector<int> len2(size, 1);
    
    for (int i = 1; i < size; i++) {
       int maxLen = 0;
       for (int j = 0; j < i; j++) {
           if (a[i] > a[j] && len1[j]+1 > maxLen) {
               maxLen = len1[j]+1;   
               len1[i] = maxLen;
           }
       }
    }
    for (int i = 0; i < len1.size(); i++) 
        cout << len1[i] << " ";
    cout << endl;

    reverse(a.begin(), a.end());
    for (int i = 1; i < size; i++) {
       int maxLen = 0;
       for (int j = 0; j < i; j++) {
           if (a[i] > a[j] && len2[j]+1 > maxLen) {
               maxLen = len2[j]+1;   
               len2[i] = maxLen;
           }
       }
    }
    for (int i = 0; i < len2.size(); i++) 
        cout << len2[i] << " ";
    cout << endl;
    
    int rtn = 0;
    for (int i = 0; i < size; i++) {
        int len = len1[i] + len2[size-i] - 1;
        rtn = max(len, rtn);
    }

    cout << rtn << endl;
    return rtn;
}


int main(int argc, char **argv)
{
    cout << "-----------------Test 1--------------------" << endl;
    int test1[] = {1, 11, 2, 10, 4, 5, 2, 1};
    int len = getSeq(test1, sizeof(test1)/sizeof(int));

    cout << "-----------------Test 2--------------------" << endl;
    int test2[] = {12, 11, 40, 5, 3, 1};
    len = getSeq(test2, sizeof(test2)/sizeof(int));

    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
